// Created by 11372 on 2021/12/15 9:50
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：84 ms, 在所有 C++ 提交中击败了89.05%的用户
 * 内存消耗：41.3 MB, 在所有 C++ 提交中击败了91.17%的用户
 */
class Solution {
public:
    vector<vector<int>> g;
    vector<int> w;
    vector<int> ans;

    vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) {

        int n = quiet.size();
        w = quiet;
        g.resize(n);
        ans.resize(n, -1);
        for (auto &e : richer) {
            int a = e[0], b = e[1];
            g[b].push_back(a);
        }
        for (int i = 0; i < n; i++) dfs(i);
        return ans;
    }

    void dfs(int u) {
        if (ans[u] != -1) return;

        ans[u] = u;
        for (auto v : g[u]) {
            dfs(v);
            if (w[ans[u]] > w[ans[v]])
                ans[u] = ans[v];
        }
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> richer = {
            {1, 0},
            {2, 1},
            {3, 1},
            {3, 7},
            {4, 3},
            {5, 3},
            {6, 3}
    };
    vector<int> quiet = {3, 2, 5, 4, 6, 1, 7, 0};
    OutputBasicArray1D(Solution().loudAndRich(richer, quiet));

    return 0;
}
